package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 并查集
 */
public class T685 {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        Map<Integer, Integer> c_p = new HashMap<>();
        Map<Integer, List<Integer>> p_c = new HashMap<>();

        int[] result = new int[2];
        for(int i = 0 ;i< edges.length;i++){
            int parent = edges[i][0];
            int child = edges[i][1];

            while(c_p.get(parent)!=null){
                parent = c_p.get(parent);
            }
            c_p.put(child, parent);
//            p_c.getOrDefault(parent,new ArrayList<>()).add(child);
        }

        f(1, p_c, c_p);
        Map.Entry<Integer, Integer> integerIntegerEntry = c_p.entrySet().stream().filter(t -> t.getValue() != 1).findAny().get();
        result[0] = integerIntegerEntry.getValue();
        result[1] = integerIntegerEntry.getKey();

        return result;
    }

    public void f(Integer root, Map<Integer, List<Integer>> p_c ,Map<Integer, Integer> c_p){
        if(p_c.get(root)==null){
            return;
        }
        for (Integer integer : p_c.get(root)) {
            c_p.put(integer, 1);
            f(integer, p_c, c_p);
        }
    }




    public static void main(String[] args) {
//        int[][] edges = {{1,2}, {1,3}, {2,3}};
//        int[][] edges = {{1,2},{2,3},{3,4},{4,1},{1,5}};
        int[][] edges = {{2,1},{3,1},{4,2},{1,4}};
        T685 t685 = new T685();
        int[] redundantDirectedConnection = t685.findRedundantDirectedConnection(edges);
        System.out.println(redundantDirectedConnection);
    }

}
